package com.ly.algorithm.leetcode.tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Classname Problem111
 * @Description
 *
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 示例 2：
 *
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 *
 * @Date 2020/12/29 14:19
 * @Author 冷心影翼
 */
public class Problem111 {

	public static void main(String[] args) {
		Solution111 solution111 = new Solution111();
		TreeNode init = TreeNode.init(new int[]{3, 9, 20, -1, -1, 15, 7});
		TreeNode init2 = TreeNode.init(new int[]{2,-1,3,-1,4,-1,5,-1,6});
		System.out.println(solution111.minDepth(init));
		System.out.println(solution111.minDepth(init2));
	}
}


class Solution111 {
	public int minDepth(TreeNode root) {
		if(root == null)
			return 0;
		ArrayDeque<TreeNode> queue = new ArrayDeque<>();
		queue.add(root);
		int deep = 1;
		while (!queue.isEmpty()) {
			int max = 0;
//			TreeNode pop = queue.pop();
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.pop();
				if(node.left == null && node.right == null) {
					return deep;
				}
				if(node.left != null) {
					queue.add(node.left);
				}
				if(node.right != null) {
					queue.add(node.right);
				}
				max++;
			}
			deep++;
//			queue.add(pop.left);
//			queue.add(pop.right);
		}
		return deep;
	}
}
